package com.exer.basic.customhash;


/**
 * 自己定义HashMap
 *
 * @param <K>
 * @param <V>
 */
public class HashMap<K, V> implements Map<K, V> {

    //存储元素对象
    private Entry<K, V> table[] = null;

    //扩容初始化
    int size = 0;

    //初始化存储元素对象大小
    public HashMap() {
        this.table = new Entry[16];
    }

    /**
     * 1.通过key hash 算法算出hash值,然后取模
     * 2.取模后就有对应的index 数组下标,然后存储对象<Entry>
     * 3.判断当前对象是否为空，如果空，直接存储，
     * 4.如果不为空，我们就要用到next 链表
     * 5.返回当前这个节点
     *
     * @param k
     * @param v
     * @return
     */
    @Override
    public V put(K k, V v) {
        int index = hash(k);
        Entry<K, V> entry = table[index];
        if (null == entry) {
            //刘一，陈二，李四，王五 就开始存在这个entry,每个entry对象则存储到了对应table 中
            table[index] = new Entry<>(k, v, index, null);
            size++;
        } else {
            //冲突了，张三，Monkey
            table[index] = new Entry<>(k, v, index, entry);
        }

        return table[index].getValue();
    }

    private int hash(K k) {
        //HashMap 底层用到的是移位的操作，性能高很多 >>,我们这里就直接取模
        int index = k.hashCode() % 16;
        //Math.abs(index);
        return index > 0 ? index : -index;
    }

    /**
     * 1.通过 key 进行hash 运算，取模，找到数组对应的下标 index
     * 2.判断当前对象是否为空,如果不为空
     * 3.判断是否相等，如果不相等
     * 4.判断next 是否为空，如果不为空，
     * 5.再判断相等，知道相等为止，或者为空为止
     * 6.然后返回
     *
     * @param k
     * @return
     */
    @Override
    public V get(K k) {
        //如果没有存储数据那size 为0，也不用查了，直接返回null
        if (size == 0) {
            return null;
        }
        int index = hash(k);
        Entry<K, V> entry = findValue(table[index], k);
        //通过index 找打这个对象
        return entry == null ? null : entry.getValue();
    }

    /**
     * @param entry
     * @param k     查询刘一
     * @return
     */
    private Entry<K, V> findValue(Entry<K, V> entry, K k) {
        //存的可能是数值类型，也可能是字符串类型
        if (k.equals(entry.getKey()) || k == entry.getKey()) {
            return entry;
            //如果不相等，估计这个节点是个链表，判断它next 数据是否匹配
        } else {
            if (entry.next != null) {
                //用到递归，在链表里面一直查询这个k,值是否相等
                return findValue(entry.next, k);
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size++;
    }


    class Entry<K, V> implements Map.Entry<K, V> {

        //存四个值
        K k;
        V v;
        int hash;
        Entry<K, V> next;

        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }

}

